import javax.lang.model.type.ArrayType;
import java.util.ArrayList;

/**
 * @author 汤奇
 * @version V1.0
 * @Project BookPro
 * @Package PACKAGE_NAME
 * @Description: 逆序单向列表
 * @Date 2022/7/25 21:41
 */
public class Test04 {
    public static void main(String[] args) {
        Node<Integer> top = new Node<>();
        Node<Integer> p = top;
        for (int i = 1; i < 10; i++) {
            p.value = i;

            if (i == 9)
                break;
            p.next = new Node<>();
            p = p.next;
        }
        print(top);

//        print(f2(top));
        print(f3(top));
//        print(f(top));
    }

    /**
     * 两个指针使链表逆序
     * @param top
     * @return
     */
    private static Node f3(Node top){
        Node p2 = top.next;
        Node p3 = top.next.next;

        //防止最后1,2循环
        top.next = null;
        for (;;){
            p2.next = top;
            if (p3 == null)
                break;
            top = p2;
            p2 =p3;
            p3 = p3.next;
        }
        return p2;

    }
    /**
     * 三个指针的逆序链表
     * @param top
     * @return
     */
    private static Node f2(Node top){
        Node p1 = top;
        Node p2 = top.next;
        Node p3 = top.next.next;

        //防止最后1,2循环
        p1.next = null;
        for (;;){
            p2.next = p1;
            if (p3 == null)
                break;
            p1 = p2;
            p2 = p3;
            p3 = p3.next;
        }
        return p2;
    }

    /**
     * 逆序链表
     * @param top 入参是一个链表的头指针
     * @return 出参是逆序后的链表
     */
    private static Node f(Node top){
        ArrayList<Node> nodes = new ArrayList<>();
        Node p = top;
        for (;;){
            if (p != null){
                nodes.add(p);
                p= p.next;
            } else {
                break;
            }
        }

        Node newTop = null;
        Node newTopP = null;
        for (;;){
            Node node = nodes.get(nodes.size() - 1);
            nodes.remove(nodes.size() - 1);

            if (newTop == null){
                newTop = node;
                newTopP = node;
            } else {
                newTopP.next = node;
                newTopP= newTopP.next;
            }

            if (nodes.size() == 0){
                newTopP.next = null;
                break;
            }
        }
        return newTop;
    }

    private static void print(Node top) {
        Node p = top;

        for (;;){
            if (p == null){
                break;
            }
            System.out.print(p.value+" ");
            p = p.next;
        }
        System.out.println();
    }

    static class Node<T>{
        T value;
        Node<T> next;
    }
}
